class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    TreeNode *lastNode;
    void flatten(TreeNode *root) {
        if (!root)
        {
            return;
        }
        // 法一：左子树的最右一个结点连到右子树 335 ms
        // while (root)
        // {
        //   if (root->left)
        //   {
        //       TreeNode *pre = root->left;
        //       while (pre->right)
        //       {
        //           pre=pre->right;
        //       }
        //       pre->right=root->right;
        //       root->right=root->left;
        //       root->left=NULL;
        //   }
        //   root=root->right;
        // }
        
        // 法二：递归，额外空间
        // if (lastNode)
        // {
        //     lastNode->right=root;
        //     lastNode->left=NULL;
        // }
        // lastNode=root;
        // TreeNode *r=root->right;
        // flatten(root->left);
        // flatten(r);
        
        // 法三：栈，额外空间
        stack<TreeNode*> s;
        TreeNode *tmp = root;
        s.push(root);
        while (!s.empty())
        {
            tmp = s.top();
            s.pop();
            if (tmp->right)
            {
                s.push(tmp->right);
            }
            if (tmp->left)
            {
                s.push(tmp->left);
            }
            // tmp->right=tmp->left;
            // tmp->left=NULL; 错。如果tmp->left本来就是null。
            tmp->left=NULL;
            if (s.empty())
            {
                tmp->right=NULL;
            }
            else
            {
                tmp->right=s.top();
            }

        }
    }
};